package com.example.websocket.sort;

import java.util.Arrays;

/**
 * 插入排序，直接插入前后依次比较进行交换，二分查找法可以减少比较操作的数目。
 * --------------------------------------------------------------------
 *   简单插入排序：
 *   在最好情况下，需要比较n-1次，无需交换元素，时间复杂度为O(n);
 *   在最坏情况下，时间复杂度依然为O(n2)。
 *
 *   二分查找：
 *   最好情况：查找的位置是有序区的最后一位后面一位，则无须进行后移赋值操作，其比较次数为：log2n  。即O(log2n)
 *   最坏情况：查找的位置是有序区的第一个位置，则需要的比较次数为：log2n，需要的赋值操作次数为n(n-1)/2加上 (n-1) 次。即O(n^2)
 *
 *   希尔排序：
 *   最好情况：序列是升序排列，在这种情况下，需要进行的比较操作需（n-1）次。后移赋值操作为0次。即O(n)
 *   最坏情况：O(nlog2n)。
 */
public class InsertionSort {

    /**
     * 直接插入
     * @param nums
     */
    public void insertion(int[] nums) {
        int length = nums.length;
        for (int i = 1; i < length; i++) {
            int temp = nums[i];
            for (int j = i; j > 0; j--) {
                if (nums[j - 1] > temp) {
                    nums[j] = nums[j - 1];
                    nums[j - 1] = temp;
                } else {
                    break;
                }
            }
        }
    }

    /**
     * 减少交换次数
     * @param nums
     */
    public void insertion1(int[] nums) {
        int length = nums.length;
        for (int i = 1; i < length; i++) {
            int temp = nums[i];
            for (int j = i; j >= 0; j--) {
                if (j > 0 && nums[j - 1] > temp) {
                    // 将大于目标值的数往后移动
                    nums[j] = nums[j - 1];
                } else {
                    // 直到找到适合位置再将值放入
                    nums[j] = temp;
                    break;
                }
            }
        }
    }

    public int binarySearch(int[] nums, int start, int end, int target) {
        while (start <= end) {
            int mid = (int) Math.floor((start + end) / 2);
            if (nums[mid] < target) {
                if (target <= nums[mid + 1]){
                    return mid + 1;
                } else {
                    start = mid + 1;
                }
            } else {
                if (end == 0) {
                    return 0;
                } else {
                    end = mid;
                }
            }
        }
        return -1;
    }

    public void insertion2(int[] nums) {
        int length = nums.length;
        int k;
        for (int i = 1; i < length; i++) {
            int temp = nums[i];
            if (nums[i - 1] < temp) {
                k = i;
            } else {
                k = binarySearch(nums, 0, i - 1, temp);
                for (int j = i; j > k; j--) {
                    nums[j] = nums[j - 1];
                }
            }
            nums[k] = temp;
        }
    }

    public static void main(String[] args) {
        int[] array = new int[]{5, 6, 3, 1, 8, 7, 2, 4};
        InsertionSort i = new InsertionSort();
        long start = System.nanoTime();
        i.insertion(array);
//        i.insertion1(array);
//        i.insertion2(array);
        long end = System.nanoTime();
        System.out.println("程序运行时间为：" + (end - start) + "ms");
        System.out.println(Arrays.toString(array));
    }
}
